A computer network is a collection of interconnected computing devices that exchange data and share resources. In a packet-based network, such as the Internet, the computing devices communicate data by dividing the data into small blocks called packets. The packets are individually routed across the network from a source device to a destination device. The destination device extracts the data from the packets and assembles the data into its original form. Dividing the data into packets enables the source device to resend only those individual packets that may be lost during transmission.
One type of computer device within the computer network, referred to a router, is responsible for routing the individual packets through the computer network from the source device that originated each packet to a destination device to which the packet is destined. To route the packets, each router of the computer network may store information describing routes through the network from each source device to each destination device. The routes may comprise a plurality of “hops” through the network, with the first hop of each route identifying the source, followed by one or more intermediate hops for each route identifying intermediate devices (such as the routers), and a final hop for each route identifying the destination. The routers may implement a routing protocol, such as a Border Gateway Protocol (BGP), to exchange routes with one another and thereby learn of all routes within the computer network, which may be referred to as the network topology.
After learning of this network topology, each of the routers may resolve the network topology to select a single path by which to reach a given destination from a given source. Often, a plurality of routes may be used to reach a given destination from a source, and each of the routers may select one of these overlapping routes through a process referred to as route resolution. The routers may perform a default form of route resolution defined by the particular routing protocol implemented by each of the routers or may alternatively perform a customized form of route resolution.
To customize the route resolution process, a network administrator or other user may define policies that influence the router's selection of routes during route resolution. For example, an administrator may define policies relating to the degree of trust for the peer from which the route was learned, for instance depending on whether the origin has been validated or is unknown or invalid. As another example, the administrator may define a policy forcing routing decisions to consider whether a route originated from a customer, peer, or transit provider. As a result, the router is often forced to evaluate a rich and complex set of variables when performing route resolution to rank and select routes. While customization may enable the network administrator to tailor how the router performs route resolution, for example, to meet particular contractual business agreements or obligations, defining and maintaining these policies may further burden already overburdened network administrators.
Although policies can be quite rich in terms of how to match routes, a challenge exists in determining the preference to be assigned to the routes, since they must ultimately be ranked by the routing protocol. Moreover, many conventional routing protocols (BGP, for example) are not particularly flexible in terms of allowing arbitrary ranking according to arbitrary criteria which were not considered ab initio. Thus, policies attempting to define complex ranking of routes often end up forcing the administrator to define exhaustive enumerations for the cross-product of all states and variables under consideration. Such policies may grow quite large and become unmanageable, especially from a human factors perspective, but also in terms of machine resources.
For example, consider the following pseudo-code to define a policy that assigns a local preference value based on a number or variables V1-VN with each variable having “M” states, S1-SM:
policy { when [(V1 == S1) && (V2 == S1) && ... (VN == S1)] then local_pref = 1; when [(V1 == S2) && (V2 == S1) && ... (VN == S1)] then local_pref = 2; when [(V1 == S2) && (V2 == S2) && ... (VN == S1)] then local_pref = 3; ... when [(V1 == SM) && (V2 == SM) && ... (VN == SM)] then local_pref = N*M;} end policy;Considering the above pseudo-code used to define the policy, a number of local preference instantiations are required to be defined so as to account for each combination of variables of the states, S1-SM, of variables, V1-VN. In particular, as noted above, this example policy consists of a number of lines to define the local preference value equal to the cross product of the number of states, M, and the number of variables, N. Consequently, these types of policies may grow quite large and become unmanageable, especially from a human factors perspective, but also in terms of machine resources.